1. Field of the Invention
The invention relates to a method of arithmetically decoding an arithmetically encoded information signal into an information signal comprising a serial sequence of n-bit symbols, where n is an integer and n=1, the method comprising the steps of:    (a) receiving the arithmetically encoded information signal,    (b) retrieving, from finite-size first and second registers, values for an A and a C parameter, respectively, the A parameter having a relationship with the size of a value interval, the C parameter having a relationship with a boundary of said interval,    (c) generating at least one probability value for an associated symbol to be decoded,    (d) deriving a symbol in response to the at least one probability value, and in response to the values for A and C retrieved from said first and second registers, respectively,    (e) updating at least the A parameter in order to obtain the new size of the interval for decoding the next symbol of the information signal,    (i) outputting the decoded symbol,    (j) as the case may be,            renormalizing the updated A parameter so as to obtain a renormalized A parameter, and        updating the C parameter so as to obtain an updated C parameter,            (k) storing the A parameter and the C parameter obtained in step    (j) in the first register and the second register, respectively.
The invention also relates to an apparatus for decoding the arithmetically encoded information signal.
2. Description Of The Related Art
The method defined in the opening paragraph is known from International Patent Application No. WO 99/49579, corresponding to U.S. Pat. No. 6,144,320 (PHN 16.822). Arithmetic coding is a well-known technique for lossless coding, and an introduction can be found in any current source-coding book. For a thorough understanding of the implementations of arithmetic coding that are most relevant for the current work, the reader is referred to [Lang84]. The history of arithmetic coding is comprehensively described in the appendix of said document.
The known method sequentially decodes symbols retrieved from the encoded information signal so as to obtain decoded symbols. The implementation of arithmetic coding, that is the subject of the present invention, uses two finite-size registers, which are usually called C and A. The decoder flow diagram is shown in FIG. 1. FIG. 2 shows the flow diagram for the “Output symbol . . . ” block shown in FIG. 1, for the case binary symbols have to be decoded. MPS and LPS are the most probable symbol and least probable symbol, respectively. Parameter p is the probability of the LPS. The value of the bit that is decoded is put in b. FIG. 3 shows a flow diagram of the decoder block denoted “Renormalize . . . ” in FIG. 1. The blocks in the decoder flow diagram in FIG. 1 are normally implemented in dedicated hardware to enable the received information to be decoded signal real-time. FIG. 1 shows a loop. When the decoding process executes the loop one time, one decoded symbol is outputted. The time needed to obtain one decoded symbol depends on the time needed to execute the three operations in the loop shown in FIG. 1. The execution of an operation should not be started until the execution of a previous operation in the loop has been finalized. To decrease the execution time, the decoder is implemented in dedicated hardware. In a software implementation, the execution time of the “Renormalize A . . . ” block is related to the value of the A parameter. FIG. 3 shows that depending on the value of A, the loop has to be executed a number of times. For example, for the application of SACD, the maximum number of times the loop may be executed is seven times. However, when implemented in dedicated hardware, the execution time is related to the worst case situation and thus to the situation the loop has to be executed that the maximum number of times. Since the worst case situation occurs only a few times in the decoding process, the “Renormalize A . . . ” block is a limiting factor for the time needed to sequentially obtain one decoded symbol.